# include <bits/stdc++.h>

const int N=100010,INF=0x3f3f3f3f,mod=998244353;

inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-') f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}

int C,T;

namespace brute{
int n,m;
int u[N],v[N];
int eu[N],ev[N],ec;

int dis[7][7];

int mx,ways;

inline void chk(int msk){
	
//	printf("kimo\n");
	
	memset(dis,INF,sizeof(dis));
	for(int i=1;i<=ec;++i){
		if((msk>>(i-1))&1){
			dis[eu[i]][ev[i]]=dis[ev[i]][eu[i]]=1;
//			printf("%d %d\n",eu[i],ev[i]);
		}
	}
//	return;
	
	for(int i=1;i<=n;++i) dis[i][i]=0;
	for(int k=1;k<=n;++k) for(int i=1;i<=n;++i) for(int j=1;j<=n;++j)
		dis[i][j]=std::min(dis[i][j],dis[i][k]+dis[k][j]);
	int cur=0;
	for(int i=1;i<=m;++i){
		if(dis[u[i]][v[i]]==INF) return;
		cur+=dis[u[i]][v[i]];
	}
	if(mx>cur) mx=cur,ways=1;
	else if(mx==cur) ++ways;
	
//	if(cur==6){
//		for(int i=1;i<=ec;++i){
//			if((msk>>(i-1))&1) printf("(%d -> %d)\n",eu[i],ev[i]); 
//		}
//		
//	}
	
	return;
}

inline void solve(void){
	n=read(),m=read(),mx=INF,ways=0;
	for(int i=1;i<=m;++i) u[i]=read(),v[i]=read();
	ec=0;
	for(int i=1;i<=n;++i){
		for(int j=i+1;j<=n;++j) ++ec,eu[ec]=i,ev[ec]=j;
	}
	int mask=(1<<ec)-1;
	for(int s=0;s<=mask;++s){
		if(__builtin_popcount(s)!=m-1) continue;
		chk(s);
	}
	printf("%d %d\n",-mx,ways);
	
	return; 
}

}

namespace circ{
inline void solve(void){
	int n=read(),m=read();
	while(m--) read(),read();
	printf("%d %d\n",-(2*n-2),1);
	return;
}
}

int main(void){
	freopen("oi.in","r",stdin);
	freopen("oi.out","w",stdout);
	
	C=read(),T=read();
	
	while(T--){
		if(C<=2) brute::solve();
		else circ::solve();
	}	


	return 0;
}

